Hyperbolic Polynomials Approach to Van der Waerden/Schrijver-Valiant like Conjectures : Sharper Bounds, Simpler Proofs and Algorithmic Applications

摘要

Let $p(x_1,...,x_n) = p(X), X \in R^{n}$ be a homogeneous polynomial ofdegree $n$ in $n$ real variables, $e = (1,1,..,1) \in R^n$ be a vector of allones . Such polynomial $p$ is called $e$-hyperbolic if for all real vectors $X\in R^{n}$ the univariate polynomial equation $P(te - X) = 0$ has all realroots $\lambda_{1}(X) \geq ... \geq \lambda_{n}(X)$ . The number of nonzeroroots $|\{i :\lambda_{i}(X) \neq 0 \}|$ is called $Rank_{p}(X)$ . A$e$-hyperbolic polynomial $p$ is called $POS$-hyperbolic if roots of vectors $X\in R^{n}_{+}$ with nonnegative coordinates are also nonnegative (the orthant$R^{n}_{+}$ belongs to the hyperbolic cone) and $p(e) > 0$ . Below$\{e_1,...,e_n\}$ stands for the canonical orthogonal basis in $R^{n}$. Themain results states that if $p(x_1,x_2,...,x_n)$ is a $POS$-hyperbolic(homogeneous) polynomial of degree $n$, $Rank_{p} (e_{i}) = R_i$ and $p(x_1,x_2,...,x_n) \geq \prod_{1 \leq i \leq n} x_i ; x_i > 0, 1 \leq i \leq n, $ then the following inequality holds $$ \frac{\partial^n}{\partialx_1...\partial x_n} p(0,...,0) \geq \prod_{1 \leq i \leq n} (\frac{G_{i}-1}{G_{i}})^{G_{i} -1} (G_i = \min(R_{i}, n+1-i)) . $$ This theorem is a vast(and unifying) generalization of as the van der Waerden conjecture on thepermanents of doubly stochastic matrices as well Schrijver-Valiant conjectureon the number of perfect matchings in $k$-regular bipartite graphs . The paperis (almost) self-contained, most of the proofs can be found in the {\bfAppendices}.